A number of systems and programs are offered on the market for the design of parts or assemblies of parts, such as the one provided by the applicant under the trademark CATIA. These so-called computer-aided design (CAD) systems allow a user to construct and manipulate complex three-dimensional (3D) models of parts or assembly of parts.
Creation of 3D computer graphics involves various steps, including modeling and process steps (subdivision of base meshes, conversion into parametric surfaces, rendering . . . ).
A number of different modeling techniques can be used to create a model of an assembly. These techniques include solid modeling, wire-frame modeling, and surface modeling. Solid modeling techniques provide for topological 3D models, where the 3D model is a collection of interconnected edges and faces, for example. Geometrically, a 3D solid model is a collection of trimmed or delimited surfaces that defines a closed skin. The trimmed surfaces correspond to the topological faces bounded by the edges. The closed skin defines a bounded region of 3D space filled with the part's material. Wire-frame modeling techniques, on the other hand, can be used to represent a model as a collection of simple 3D lines, whereas surface modeling can be used to represent a model as a collection of exterior surfaces. CAD systems may combine these, and other, modeling techniques, such as parametric modeling techniques. CAD systems thus provide a representation of modeled objects using edges or lines, in certain cases with faces. The modeled objects comprises a number of lines or edges; these may be represented in various manners, e.g. non-uniform rational B-splines (NURBS), Bezier curves or other algorithms describing a curve.
Regarding process steps, CAD programs generally make use of base meshes during the modeling of objects. Base meshes are networks of interconnected elementary polygons, such as triangles or quadrangles.
A base mesh is modified by the user during design to obtain the required model, and then is converted into a plurality of parametric surfaces such as NURBS or B-Splines.
Concerning the modeled products: modern consumer products are often characterized by smoothly flowing shapes, the complexity of which exceeds simple analytical surfaces, such as planes, boxes and cylinders. Such products are instead typically modeled using spline curves and surfaces or the like. When designing a product, smoothness of object surfaces is a main concern. Consequently, 3D modelers usually have an assortment of tools for creating smooth surfaces.
In the following, “curvature” will be used as a geometry term indicating the extent that a curve or surface deviates from perfect straightness or flatness. Curvature is usually measured as the inverse of a local osculating radius. Thus, a curve has a low curvature and a large radius when it is slightly bent only, and has a high curvature and a small radius if bent sharply. While curvature is constant for arcs, circles, or for surfaces based thereon; the curvature of more complex curves such as splines (and surfaces based thereon) continually changes along the length of the curve.
Furthermore, the term “continuity” will be used for describing offsets (or relationships) between points along a curve or on a surface and also between abutting curves or surfaces. Such relationships may fall into different levels of continuity, which are usually: C0, C1, and C2. C0 denotes a position continuity only (as in the case of abutting curves/surfaces). Curves show in this case a kink at the C0 point. Similarly, surfaces have a sharp crease along the C0 seam. Abutting curves and surfaces touch one another, but they have no curvature similarities. C1 denotes a continuity level augmented with tangent continuity, and C2 adds the curvature continuity. Where curvatures on both sides of a point in a curve are equal, the curve is seamless.
In addition, it will be made reference to G0, G1, and G2 “geometrical” continuities, which slightly differ on the mathematical point of view, as known in the art. For example, two joining curve segments have Gn continuity if nth order derivatives of respective curves have the “same direction” at the join (proportionality defined by some matrix is sufficient, equality is not required). As a result, Cn implies Gn while the reciprocal is not necessarily true.
Amongst the core techniques of surface modeling, one generally makes use of piecewise low-order algebraic surfaces or implicit patches. Patches are typically controlled via a grid of control points, whereby they can be deformed. An important issue in using patches is that patches must be adequately joined to ensure geometric continuity along the patch boundaries. Typically, the patch cells are recursively subdivided to make it possible to adapt the local curvature to a given continuity requirement.
In numerous applications (such as computer graphics), subdivision surfaces such as Catmull-Clark, are used to approximate a surface derived from a base mesh. In particular, Catmull-Clark subdivision surfaces are now a standard for smooth free-form surface modeling. Subdivision surfaces are used to create smooth surfaces out of arbitrary meshes, that is, with arbitrary topology. They are defined as the limit of an infinite refinement process. A key concept is refinement: by repeatedly refining an initial polygonal mesh, a sequence of meshes is generated that converges to a resulting subdivision surface. Each new subdivision step generates a new mesh that has more polygonal elements and is smoother. In particular, Catmull-Clark subdivision surfaces can be seen as a generalization of bi-cubic uniform B-splines. An important point is that the generated mesh will mainly consist of quadrilaterals, so that the expected valence (or coordination number) of an ordinary vertex is 4. In this respect, a distinction is sometimes made between open and closed vertex. Open/closed vertices are concepts known in the art. In short: suppose a vertex v be surrounded and joined by edges E1, E2, En+1, such that En+1=E1, said vertex is considered to be closed if none of the edges is a sharp edge.
However, in the field of CAD, subdivision surfaces are not commonly accepted as they are not parametric. Thus, CAD systems provide conversion algorithms to convert a subdivision surface into a parametric surface consisting of a set of surface patches, such as NURBS patches.
Nevertheless, the resulting parametric surfaces give rise to an insufficient quality of continuity. Indeed, those surfaces are everywhere curvature continuous except at points corresponding to vertices not incident on four edges (extraordinary vertices) of the initial base mesh.
In this respect, most of existing process for creating parametric surfaces skip the continuity problem caused by extraordinary vertices.
Yet, parallel to the present invention, a method has been disclosed which involves discrete Fourier transform (C. Loop: Second Order Smoothness over Extraordinary vertices, Eurographics Symposium on Geometry Processing (2004)). However, this approach does manifestly apply to closed extraordinary vertices only.
Hence, in short, there is a need for a process for creating a parametric surface, the process simultaneously fulfilling the following conditions:                satisfying a given geometrical continuity Gi (for example G1 or G2) requirement;        being compatible with both open and closed vertices; and        using a local, linear resolution algorithm, so as to ensure its stability, should high valence vertices be contemplated.        
Furthermore, to the best of the knowledge of the inventor, whilst suggesting some features and variations relevant to creation of parametric surfaces in general, the prior art has not disclosed some of the highly advantageous features of the present invention discussed herein.